/**
 * Created by L.jp
 * Description:给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * 数据范围:
 * 3<=节点总数<=10000
 * 0<=节点值<=10000
 * User: 86189
 * Date: 2022-06-27
 * Time: 10:38
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
}
/**
 * @author 86189
 */
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //发现一个规律，如果当前节点的值比两个目标节点的值小，那么最近公共祖先在右子树
        //如果当前节点的值比两个目标节点的值大，那么最近公共祖先在左子树，如果当前节点的值
        //比两个目标值其中一个大，另一个小，那么当前节点就是最近公共祖先
        if((root.val<=p && root.val>=q)
                || (root.val<=q && root.val>=p)){
            return root.val;
        }else if(root.val<p && root.val<q){
            return lowestCommonAncestor( root.right,p,q );
        }else{
            return lowestCommonAncestor( root.left,p,q );
        }
    }
}
